package com.lw.leetcode.dp.b;

import java.util.Arrays;

/**
 * back
 * 518. 零钱兑换 II
 *
 * @Author liw
 * @Date 2021/6/30 22:18
 * @Version 1.0
 */
public class Change {

    public static void main(String[] args) {
        Change test = new Change();
//        int[] coins = {1, 2, 5};
//        int amount = 5;
//        int[] coins = {10};
//        int amount = 30;
        // 500
        //[3,5,7,8,9,10,11]   35502874
        int[] coins = {3,5,7,8,9,10,11};
        int amount = 500;
        int change = test.change4(amount, coins);
        System.out.println(change);
    }

    /*
    采用回溯算法
    1：传参sum表示当前所求的和，把他与amount做判断
        若 sum < amount,则可以继续累计。
        若 sum == amount, 则表示得到一个正确结果，count++;
     */

    private int count;
    private int[] coins;
    private int amount;
    public int change3(int amount, int[] coins) {
        if(amount == 0) {
            return 1;
        }
        Arrays.sort(coins);
        this.count = 0;
        this.coins = coins;
        this.amount = amount;
        find(0, coins.length - 1);
        return count;
    }

    private void find(int sum, int st) {
        for (int i = st; i >= 0; i--) {
            int value = sum + coins[i];
            if (value == amount) {
                count++;
            } else if (value < amount) {
                find(value, i);
            }
        }
    }



    public int change (int amount, int[] coins) {
        if(amount == 0) {
            return 1;
        }
        int length = coins.length;
        int[][] arr = new int[length + 1][amount + 1];
        for (int i = 0; i <= length; i++) {
            arr[i][0] = 1;
        }
        for (int i = 1; i <= length; i++) {
            int value = coins[i - 1];
            for (int j = 1; j <= amount; j++) {
                int sum = 0;
                for (int k = j; k >= 0; k = k - value) {
                    sum += arr[i - 1][k];
                }
                arr[i][j] = sum;
            }
        }
        return arr[length][amount];
    }

    public int change4(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }


}
